package com.test.daily.leetcode.y2022.m06.day0604.v01;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @descriptions: DirectGraphNode
 * @author: Tom
 * @date: 2022/6/4 下午 08:33
 * @version: 1.0
 */
public class Code03_TopologicalOrderBFS {
    // DirectedGraphNode
    public static class DirectedGraphNode{
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;
        public DirectedGraphNode(int label){
            this.label = label;
            neighbors = new ArrayList<>();
        }
        public static ArrayList<DirectedGraphNode> topologicalOrder(ArrayList<DirectedGraphNode> graph){
            HashMap<DirectedGraphNode, Integer> indegreeMap = new HashMap<>();
            for(DirectedGraphNode cur: graph){
                indegreeMap.put(cur, 0);
            }
            for(DirectedGraphNode cur: graph){
                for(DirectedGraphNode next: cur.neighbors){
                    indegreeMap.put(next, indegreeMap.get(next) +1);
                }
            }
            Queue<DirectedGraphNode> zeroQueue = new LinkedList<>();
            for(DirectedGraphNode cur: indegreeMap.keySet()){
                if(indegreeMap.get(cur) == 0){
                    zeroQueue.add(cur);
                }
            }
            ArrayList<DirectedGraphNode> ans = new ArrayList<>();
            while(!zeroQueue.isEmpty()){
                DirectedGraphNode cur = zeroQueue.poll();
                ans.add(cur);
                for(DirectedGraphNode next: cur.neighbors){
                    indegreeMap.put(next, indegreeMap.get(next) - 1);
                    if(indegreeMap.get(next) == 0){
                        zeroQueue.add(next);
                    }
                }
            }
            return ans;
        }
    }
}
